1. Field of the Invention
The present invention relates to a shortest path search system, and in particular to a method and a system for searching for the shortest path between multiple nodes.
2. Related Art
The problem of finding the shortest path between multiple nodes is a problem for which a set of a plurality of sources and a set of a plurality of destinations are provided, and the shortest source-destination path is found for each source paired with each of the destinations in the set of destinations. Therefore, when there are n source nodes and m destination nodes, the shortest path must be found for nxc3x97m pairs of sources and destinations. Nodes that are included in both the source set and the destination set may be present. The Dijkstra method is known as the only method available for calculating the shortest paths between a single source and multiple destinations on a directed graph having a non-negative edge length. For reference, the pseudo code of the Dijkstra method is described below.
1xc3x97NshortestPath (source s, destination set T)
Conventionally, the number of times the Dijkstra method is repeated is equivalent to the count of the multiple sources for which the shortest paths to multiple destinations are calculated. This method is also employed for various types of navigation systems. A method for increasing the speed of the Dijkstra method is not yet to be proposed.
It is, therefore, one object of the present invention to provide an efficient method and system for searching for the shortest path between a source and multiple destinations.
It is another object of the present invention to provide a method and a system for searching for the shortest paths between multiple sources and multiple destinations.
It is an additional object of the present invention to resolve a path searching problem within a short period of time when searching for the shortest path between multiple nodes.
It is a further object of the present invention to provide a search method and a search system with which optimality is not lost during a search for the shortest path between multiple nodes.
To achieve the above objects, according to the present invention, the speed of the conventional Dijkstra method, which is the basic calculation method, is increased by employing information concerning the relationship between a node and a set of destinations on a graph. The relationship information is constituted by the estimate function h(v) concerning a specific node v and a destination sets T, where h(v) is a lower bound of all the shortest path lengths extending from node v to each of the destination sets T.
In the present invention, calculation of an estimate function h(v) that satisfies the above condition is performed to obtain a value called an estimate function since an evaluation to determine the shortest path is performed during the calculation. The employment of the estimate function can increase the speed of the Dijkstra method. The lower bound is a specific value equal to or less than the smallest value.
FIG. 2 is a flowchart according to the present invention for searching for the shortest paths between a single source and multiple destinations. First, at block 210 a priority queue is prepared in which a node to be searched for is entered. At block 220 is specified a node v, entered in the priority queue, at which is minimized the sum of a path length p(v), between the source and the node v, and the lower bound h(v) of the shortest path of those for the nodes that adjoin the node v. When node v is specified in this manner, a specific direction characteristic can be provided for the extension of the search direction. At block 230, node v is deleted from the priority queue, and at block 240, node v is stored in the established set S, a set of solutions of the shortest paths. A check is then performed to determine whether all the destinations are included in the established set S (block 250). When all the destinations are stored, the shortest path search is terminated. At block 260, each node w is specified at which a path length p(w) is equal to or greater than the sum of a path length p(v) between the source and node v and a path length between node v and the specified node w. Finally, at block 270 all nodes w are entered in the priority queue, and program control returns to block 220.